package solutions.leetcode.normal

import solutions.csdn.part2
import java.util.Arrays
import java.util.LinkedList
import java.util.PriorityQueue


/**
 * @author lizhidong
 * <a href="https://leetcode.cn/problems/best-team-with-no-conflicts/">1626. 无矛盾的最佳球队</a>
 */
private class Solution1626 {
    fun bestTeamScore(scores: IntArray, ages: IntArray): Int {
        val people = Array(scores.size) { i -> intArrayOf(scores[i], ages[i]) }
        Arrays.sort(people) { o1, o2 -> if (o1[0] == o2[0]) o1[1] - o2[1] else o1[0] - o2[0] }

        val dp = IntArray(scores.size) { 0 }
        var max = 0
        for (i in people.indices) {
            var pre = 0
            for (j in i - 1 downTo 0) {
                if (people[j][1] <= people[i][1]) {
                    pre = Math.max(pre, dp[j])
                }
            }
            dp[i] = pre + people[i][0]
            max = Math.max(max, dp[i])
        }
        return max
    }
}

fun main() {
    println(
        Solution1626().bestTeamScore(
            intArrayOf(
                9, 2, 8, 8, 2
            ),
            intArrayOf(
                4, 1, 3, 3, 5
            )
        )
    )
}